package leetcode_101_120;

import utils.Node;

import java.util.ArrayList;
import java.util.List;

public class connect2_117 {
    /**
     * 填充普通二叉树每个节点的下一个右侧节点指针（next 指针）
     * 让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     * 初始状态下，所有 next 指针都被设置为 NULL。
     */
    public Node connect(Node root) {
        /**
         * 想法是与上一题一样
         * 用一个集合保存从上到下的一层节点，当遍历到左边的节点时找到集合中其对应深度的节点即可
         */
        List<Node> nodes=new ArrayList<>();
        function(root,1,nodes);
        return root;
    }
    public void function(Node root, int depth, List<Node> nodes) {
        if(root==null)
            return;

        if(depth>nodes.size())
            nodes.add(root);
        else {
            root.next=nodes.get(depth-1); //节点的右侧节点为集合中对应位置的节点
            nodes.set(depth-1,root);   //替换掉原位置的节点
        }

        function(root.right,depth+1,nodes);  //先进入右节点

        function(root.left,depth+1,nodes);
    }
}
